LOJ 6030「雅礼集训 2017 Day1」矩阵

发表于
字数统计: 607字 | 阅读时长 ≈ 3min

LOJ 6030「雅礼集训 2017 Day1」矩阵

imgimg

算是一道签到题了，但是还是要考一点点思维。

首先简化题意：每次可以用任意行去涂任意列，求把矩阵变为全黑的最少步数或判断无解。

首先考虑何时无解。矩阵一开始就全白则显然无解，而只要存在黑色格子就有解：对于一个黑格子$(i,j)$，可以先用第$i$行去涂第$j$列，使得$(j,j)$变成黑色。容易发现，只要主对角线上存在黑格子，就能用它把它所在的行全部涂黑，而只要有一行全黑，那么就可以把整个矩形涂成全黑。

然后就是一点一点去发现一些结论从而得到正解了。通过观察得到以下结论：

  1. 如果某一列存在白格子，那么这一列至少会对答案贡献1。
  2. 结合1，用不是全黑的行去涂某一列是不会使得答案减少的。
  3. 结合2，应该尽快弄出全黑的行，再用全黑的行去涂不是全黑的列。
  4. 得到第一个全黑的行之前不会增加全黑的列。
  5. 对于任意一行，一次操作最多改变一个位置的颜色。
  6. 想要把第$i$行涂成全黑，需要先使$(i,i)$为黑。在$(i,i)$初始为白，而第$i$列存在黑色的情况，仅需一次操作即可将其变黑，否则需要额外的一次把某个含有黑格子的行涂到第$i$列的操作。

综上所述，在有解的情况下，只需要枚举把哪一行涂成全黑，看一看每一行白格子的个数和对应列是否全白即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<stdio.h>
#include<algorithm>
#include<cstring>
#define MAXN 1005
using namespace std;

int N,Ans,tmp,cnt[MAXN];
char s[MAXN][MAXN];

int main(){
	int i,j,t=0;
	scanf("%d",&N);
	for(i=1;i<=N;i++)scanf("%s",&s[i][1]);
	for(i=1;i<=N;i++)
	for(j=1;j<=N;j++)if(s[i][j]=='#')t++;
	if(!t)return puts("-1"),0;
	for(i=1;i<=N;i++){
		for(j=1;j<=N;j++)if(s[j][i]=='#')cnt[i]++;
		if(cnt[i]!=N)Ans++;
	}
	tmp=Ans;Ans=1e9;
	for(i=1;i<=N;i++){
		t=0;
		for(j=1;j<=N;j++)if(s[i][j]=='.')t++;
		Ans=min(tmp+t+(!cnt[i]),Ans);
	}
	printf("%d\n",Ans);
}